/*
    1. Write a C program for binary search.
    Binary Search : In computer science, a binary search or half-interval 
    search algorithm finds the position of a target value within a sorted array. 
    The binary search algorithm can be classified as a dichotomies divide-and-conquer 
    search algorithm and executes in logarithmic time.
*/

#include <stdio.h>

int binsearch(int sa[], int len, int val)
{
    int head = 0;
    int tail = len;
    int bin = (head + tail) / 2;
    int i = 0;
    
    while(i < len/2){
        if(val > sa[bin]){
            head = bin;
        }else if(val < sa[bin]){
            tail = bin;
        }else{
            return bin;
        }
        bin = (head + tail) / 2;
        i++;
    }
    printf("The value %d is not exited in this sorted array", val);
    return -1;
}

#define MAX_LEN 11

int main(void)
{
    int a[MAX_LEN] = {1, 2, 4, 6, 7, 12, 24, 43, 80, 100, 111};
    int val;
    printf("Input the value to search : ");
    scanf("%d", &val);
    int pos = binsearch(a, MAX_LEN, val);
    if(pos != -1) printf("pos = %d\n", pos);

    return 0;
}